#include <stdio.h>

void rule(int l, int r, int h);
void mark(int m, int h);
void rule_non_recursive(int l, int r, int h);

int main(){
    // // 测试给长度为8的尺子绘制标记
    // printf("Testing draw rule length 8 mark  start...\n");
    // rule(0, 8, 3);
    // printf("Testing draw rule length 8 mark  end...\n");

    // // 测试给长度为16的尺子绘制标记
    // printf("Testing draw rule length 16 mark  start...\n");
    // rule(0, 16, 4);
    // printf("Testing draw rule length 16 mark  end...\n");

    // 测试给长度为8的尺子绘制标记
    printf("Testing draw rule length 8 mark  start...\n");
    rule_non_recursive(0, 8, 3);
    printf("Testing draw rule length 8 mark  end...\n");

    // 测试给长度为16的尺子绘制标记
    printf("Testing draw rule length 16 mark  start...\n");
    rule_non_recursive(0, 16, 4);
    printf("Testing draw rule length 16 mark  end...\n");
    return 0;
}

void rule(int l, int r, int h){
    int m = (l+r)/2;
    if (h > 0) {
        rule(l, m, h-1);
        mark(m, h);
        rule(m, r, h-1);
    }
}

void mark(int m, int h){
    printf("mark(%d, %d)\n", m, h);
}

/**
 * 绘制尺子标记迭代版
 * ------------------------------------------------
 * 思路：
 * 遍历标记高度，找出等于该标记高度的标记位置序列，绘制标记
 * ------------------------------------------------
 * 标记位置序列的表示：
 * 起点为2^{h-1}，步长为2*h
 * ------------------------------------------------
 */
void rule_non_recursive(int l, int r, int h){
    int t;
    int j;
    int i;
    for (t = 1, j = 1; t <= h; t++, j += j) {
        for (i = 0; l + i + j <= r; i += j+j) {
            mark(l+i+j, t);
        }
    }
}

